package leetcode.array.common;

import leetcode.string.common.StringUtils;

import java.util.*;
import java.util.stream.Collectors;

public class ArrayUtils {
    /**
     * 给定一个数组nums，将其划分为两个连续子数组left和right，使得：
     * <p>
     * left中的每个元素都小于或等于right中的每个元素。
     * left 和right都是非空的。
     * left 的长度要尽可能小。
     * 在完成这样的分组后返回left的长度。
     *
     * @param nums
     * @return
     */
    public static int partitionDisjoint(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        // 初始化左边部分边界
        int index = findMinValueOfList(nums, start, end);
        while (true) {
            if (index > nums.length - 1) {
                break;
            }
            // 找到当前左边部分的最大值
            int maxIndex = findMaxValueOfList(nums, 0, index);
            int maxVal = nums[maxIndex];
            // 找到右边部分比左边最大值小的数
            int lessNumIndex = findLessNumOfListThanVal(nums, index + 1, nums.length - 1, maxVal);
            // 如果右边找不到比左边最大值小的数, 循环结束, 返回当前左边部分边界
            if (lessNumIndex == -1) {
                break;
            }
            // 刷新左边部分边界
            index = lessNumIndex;
        }
        return index + 1;
    }

    /**
     * 找到指定范围中最大的那个数
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private static int findMaxValueOfList(int[] nums, int start, int end) {
        int maxIndex = -1;
        int maxValue = Integer.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    /**
     * 返回值是符合要求的数的索引
     *
     * @param nums
     * @param maxVal
     * @return
     */
    private static int findLessNumOfListThanVal(int[] nums, int start, int end, int maxVal) {

        // 找到右边部分最靠右的那个数
        // 从右向左遍历
        for (int i = end; i >= start; i--) {
            if (nums[i] < maxVal) {
                return i;
            }
        }
        // 找不到符合要求的数
        return -1;
    }

    /**
     * 找到指定部分中最小的那个数
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private static int findMinValueOfList(int[] nums, int start, int end) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i = start; i <= end; i++) {
            if (nums[i] < min) {
                min = nums[i];
                index = i;
            }
        }
        return index;
    }

    public static int[] plusOne(int[] digits) {
        int curIndex = digits.length - 1;
        return solvePlusOne(digits, curIndex);
    }

    private static int[] solvePlusOne(int[] digits, int curIndex) {
        if (digits[curIndex] != 9) {
            digits[curIndex]++;
            return digits;
        } else {
            if (curIndex == 0) {
                int[] temp = new int[digits.length + 1];
                temp[0] = 1;
                temp[1] = 0;
                for (int i = 2; i < temp.length; i++) {
                    temp[i] = digits[i - 1];
                }
                return temp;
            } else {
                digits[curIndex] = 0;
                return solvePlusOne(digits, curIndex - 1);
            }
        }
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        m--;
        n--;
        int i = nums1.length - 1;
        while (i >= 0) {
            if (m >= 0 && n >= 0) {
                if (nums1[m] >= nums2[n]) {
                    nums1[i] = nums1[m];
                    m--;
                } else {
                    nums1[i] = nums2[n];
                    n--;
                }
            } else {
                if (n >= 0) {
                    nums1[i] = nums2[n];
                    n--;
                }
                if (m >= 0) {
                    nums1[i] = nums1[m];
                    m--;
                }
            }
            i--;
        }
    }

    public static String addBinary(String a, String b) {
        if ((a == null || a.length() == 0) && (b == null || b.length() == 0)) {
            return "";
        }
        if (a == null || a.length() == 0) {
            return b;
        }
        if (b == null || b.length() == 0) {
            return a;
        }
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        StringUtils.reverseCharArray(aArray);
        StringUtils.reverseCharArray(bArray);
        int[] result = new int[Math.max(a.length(), b.length()) + 1];
        int curIndex = 0;
        solveAddBinary(aArray, bArray, curIndex, result);
        String s = "";
        if (result[result.length - 1] == 1) {
            s = s + result[result.length - 1];
        }
        for (int i = result.length - 2; i >= 0; i--) {
            s = s + result[i];
        }
        return s;
    }

    private static void solveAddBinary(char[] aArray, char[] bArray, int curIndex, int[] result) {
        if (curIndex == result.length - 1) {
            return;
        }
        int sum = 0;
        if (curIndex < aArray.length) {
            sum = sum + Integer.parseInt(String.valueOf(aArray[curIndex]));
        }
        if (curIndex < bArray.length) {
            sum = sum + Integer.parseInt(String.valueOf(bArray[curIndex]));
        }
        sum = sum + result[curIndex];
        result[curIndex] = sum % 2;
        result[curIndex + 1] = sum / 2;
        solveAddBinary(aArray, bArray, curIndex + 1, result);
    }

    public static List<Integer> arrayToList(Integer[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        list.addAll(Arrays.asList(nums));
        return list;
    }

    public static List<Integer> intArrayToList(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        return list;
    }

    public static boolean containsDuplicate(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int num : nums) {
            if (map.get(num) == null) {
                map.put(num, true);
            } else {
                return true;
            }
        }
        return false;
    }

    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[(nums.length - 1) / 2];
    }

    public static int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            maxProfit = Math.max(prices[i] - minPrice, maxProfit);
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
        }
        return maxProfit;
    }

    public static int minMaxGame(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] newNums = new int[nums.length / 2];
        for (int i = 0; i < newNums.length; i++) {
            if (i % 2 == 0) {
                newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
            } else {
                newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
            }
        }
        return minMaxGame(newNums);
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k >= nums.length) {
            Map<Integer, Boolean> map = new HashMap<>();
            for (int num : nums) {
                if (map.get(num) == null) {
                    map.put(num, true);
                } else {
                    return true;
                }
            }
            return false;
        }

        int left = 0;
        int right = k;

        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = left; i <= right; i++) {
            if (map.get(nums[i]) == null) {
                map.put(nums[i], true);
            } else {
                return true;
            }
        }

        right++;
        while (right < nums.length) {
            map.remove(nums[left]);
            if (map.get(nums[right]) != null) {
                return true;
            }
            map.put(nums[right], true);
            left++;
            right++;
        }
        return false;
    }

    public static List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums.length == 0) {
            return result;
        }
        if (nums.length == 1) {
            String s = String.valueOf(nums[0]);
            result.add(s);
            return result;
        }
        int start = 0;
        int end = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[end] + 1) {
                String s;
                if (start != end) {
                    s = nums[start] + "->" + nums[end];
                } else {
                    s = String.valueOf(nums[start]);
                }
                result.add(s);
                start = i;
                end = i;
            } else {
                end++;
            }
        }
        String s;
        if (start != end) {
            s = nums[start] + "->" + nums[end];
        } else {
            s = String.valueOf(nums[start]);
        }
        result.add(s);
        return result;
    }

    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int[] map = new int[n + 1];
        for (int num : nums) {
            map[num]++;
        }
        for (int i = 0; i < n + 1; i++) {
            if (map[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    public static int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        boolean[] show = new boolean[1005];
        boolean[] show2 = new boolean[1005];
        for (int j : nums1) {
            show[j] = true;
        }
        for (int j : nums2) {
            if (show[j] && !show2[j]) {
                list.add(j);
            }
            show2[j] = true;
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public static int[] intersect(int[] nums1, int[] nums2) {

        List<Integer> list = new ArrayList<>();
        int[] show = new int[1005];
        for (int j : nums1) {
            show[j]++;
        }
        for (int j : nums2) {
            if (show[j] > 0) {
                list.add(j);
                show[j]--;
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public static List<Integer> findDisappearedNumbers(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            if (map.getOrDefault(i, 0) == 0) {
                result.add(i);
            }
        }
        return result;
    }

    public static int dominantIndex(int[] nums) {
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[index]) {
                index = i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i == index) {
                continue;
            }
            if (nums[index] < nums[i] * 2) {
                return -1;
            }
        }
        return index;
    }

    public static int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i] * nums[i];
        }
        Arrays.sort(result);
        return result;
    }

    public static int[] findErrorNums(int[] nums) {
        Map<Integer, Boolean> show = new HashMap<>();
        int[] result = new int[2];
        for (int num : nums) {
            if (show.getOrDefault(num, false)) {
                result[0] = num;
            }
            show.put(num, true);
        }
        for (int i = 1; i < nums.length + 1; i++) {
            if (!show.getOrDefault(i, false)) {
                result[1] = i;
                break;
            }
        }
        return result;
    }

    public static int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        int maxTime = 0;
        for (Integer num : map.keySet()) {
            Integer time = map.getOrDefault(num, 0);
            if (time > maxTime) {
                maxTime = time;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (Integer num : map.keySet()) {
            Integer time = map.getOrDefault(num, 0);
            if (time != maxTime) {
                continue;
            }
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                if (nums[left] == num && nums[right] == num) {
                    list.add(right - left + 1);
                    break;
                }
                if (nums[left] != num) {
                    left++;
                }
                if (nums[right] != num) {
                    right--;
                }
            }
        }
        Collections.sort(list);
        if (!list.isEmpty()) {
            return list.get(0);
        } else {
            return -1;
        }
    }

    public static boolean isMonotonic(int[] nums) {
        if (nums.length <= 2) {
            return true;
        }
        boolean asc = false;
        boolean desc = false;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                asc = true;
            }
            if (nums[i] < nums[i - 1]) {
                desc = true;
            }
            if (asc && desc) {
                return false;
            }
        }
        return true;
    }

    /**
     * 确保 nums。length 长度是偶数
     *
     * @param nums
     * @return
     */
    public static int[] sortArrayByParityII(int[] nums) {
        // 检查偶数位
        int left = 0;
        // 检查奇数位
        int n = nums.length;
        int right = n - 1;
        while (left <= n - 1 && right >= 0) {
            while (left <= n - 1) {
                // 如果偶数位数字是奇数,退出循环
                if (nums[left] % 2 != 0) {
                    break;
                }
                left += 2;
            }
            while (right >= 0) {
                // 如果奇数位数字是偶数,退出循环
                if (nums[right] % 2 == 0) {
                    break;
                }
                right -= 2;
            }
            if (left >= n || right < 0) {
                break;
            }
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left += 2;
            right -= 2;
        }
        return nums;
    }

    public static List<Integer> addToArrayForm(int[] num, int k) {
        int[] array = reverseIntArray(num);
        List<Integer> list = new ArrayList<>();
        while (k > 0) {
            list.add(k % 10);
            k /= 10;
        }
        int[] kArray = convertListToArray(list);
        int n = Math.max(array.length, kArray.length);
        int[] result = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int sum = result[i];
            if (i < array.length) {
                sum += Integer.parseInt(String.valueOf(array[i]));
            }
            if (i < kArray.length) {
                sum += Integer.parseInt(String.valueOf(kArray[i]));
            }
            result[i] = sum % 10;
            result[i + 1] = sum / 10;
        }
        result = reverseIntArray(result);
        if (result[0] == 0) {
            int[] ints = new int[n];
            System.arraycopy(result, 1, ints, 0, n);
            result = ints;
        }
        return Arrays.stream(result).boxed().collect(Collectors.toList());
    }

    private static int[] reverseIntArray(int[] num) {
        List<Integer> list = convertArrayToList(num);
        Collections.reverse(list);
        return convertListToArray(list);
    }

    /**
     * 将list转为int数组
     *
     * @param list
     * @return
     */
    public static int[] convertListToArray(List<Integer> list) {
        return list.stream().mapToInt(i -> i).toArray();
    }

    /**
     * 将int数组转为list
     *
     * @param num
     * @return
     */
    public static List<Integer> convertArrayToList(int[] num) {
        return Arrays.stream(num).boxed().collect(Collectors.toList());
    }

    public static List<Integer> countSmaller(int[] nums) {
        int[] result = new int[nums.length];
        result[nums.length - 1] = 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            for (int j = i + 1; j <= nums.length - 1; j++) {
                if (nums[j] < nums[i]) {
                    result[i]++;
                }
            }
        }
        return Arrays.stream(result).boxed().collect(Collectors.toList());
    }

    public static boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }

    public static int minMeetingRooms(int[][] intervals) {
        int max = 1;
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        for (int i = 1; i < intervals.length; i++) {
            int count = 1;
            int curMeetingStartTime = intervals[i][0];
            for (int j = i - 1; j >= 0; j--) {
                int beforeMeetingEndTime = intervals[j][1];
                if (curMeetingStartTime < beforeMeetingEndTime) {
                    count++;
                }
            }
            max = Math.max(max, count);
        }
        return max;
    }

    public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<>();
        if (nums.length == 0) {
            String s = "";
            if (lower != upper) {
                s += lower + "->" + upper;
            } else {
                s += lower;
            }
            result.add(s);
            return result;
        }
        if (nums[0] != lower) {
            String s = "";
            if (nums[0] != lower + 1) {
                s += lower + "->" + (nums[0] - 1);
            } else {
                s += lower;
            }
            result.add(s);
        }
        for (int i = 0; i <= nums.length - 2; i++) {
            if (nums[i + 1] == nums[i] + 1) {
                continue;
            }
            String s = "";
            if (nums[i + 1] == nums[i] + 2) {
                s += (nums[i] + 1);
            } else {
                s += (nums[i] + 1) + "->" + (nums[i + 1] - 1);
            }
            result.add(s);
        }
        if (nums[nums.length - 1] != upper) {
            String s = "";
            if (nums[nums.length - 1] == upper - 1) {
                s += upper;
            } else {
                s += (nums[nums.length - 1] + 1) + "->" + upper;
            }
            result.add(s);
        }
        return result;
    }


    public static List<List<Integer>> convertArrayToList(int[][] triangle) {
        List<List<Integer>> result = new ArrayList<>();
        for (int[] ints : triangle) {
            result.add(convertArrayToList(ints));
        }
        return result;
    }

    public static int longestWPI(int[] hours) {

        int n = hours.length;
        int[] s = new int[n + 1];
        Deque<Integer> stk = new ArrayDeque<Integer>();
        stk.push(0);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
            if (s[stk.peek()] > s[i]) {
                stk.push(i);
            }
        }

        int res = 0;
        for (int r = n; r >= 1; r--) {
            while (!stk.isEmpty() && s[stk.peek()] < s[r]) {
                res = Math.max(res, r - stk.pop());
            }
        }
        return res;

    }

    public static boolean isGoodArray(int[] nums) {
        int divisor = nums[0];
        for (int num : nums) {
            divisor = gcd(divisor, num);
            if (divisor == 1) {
                break;
            }
        }
        return divisor == 1;
    }

    public static int gcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }

    public static int[] numberOfPairs(int[] nums) {

        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            } else {
                set.remove(num);
                count++;
            }
        }
        return new int[]{count, nums.length - 2 * count};

    }

    public static int largest1BorderedSquare(int[][] grid) {

        int m = grid.length, n = grid[0].length;
        int[][] left = new int[m + 1][n + 1];
        int[][] up = new int[m + 1][n + 1];
        int maxBorder = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i - 1][j - 1] == 1) {
                    left[i][j] = left[i][j - 1] + 1;
                    up[i][j] = up[i - 1][j] + 1;
                    int border = Math.min(left[i][j], up[i][j]);
                    while (left[i - border + 1][j] < border || up[i][j - border + 1] < border) {
                        border--;
                    }
                    maxBorder = Math.max(maxBorder, border);
                }
            }
        }
        return maxBorder * maxBorder;

    }

    public static double maxAverageRatio(int[][] classes, int extraStudents) {

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            long val1 = (long) (b[1] + 1) * b[1] * (a[1] - a[0]);
            long val2 = (long) (a[1] + 1) * a[1] * (b[1] - b[0]);
            if (val1 == val2) {
                return 0;
            }
            return val1 < val2 ? 1 : -1;
        });
        for (int[] c : classes) {
            pq.offer(new int[]{c[0], c[1]});
        }

        for (int i = 0; i < extraStudents; i++) {
            int[] arr = pq.poll();
            int pass = arr[0], total = arr[1];
            pq.offer(new int[]{pass + 1, total + 1});
        }

        double res = 0;
        for (int i = 0; i < classes.length; i++) {
            int[] arr = pq.poll();
            int pass = arr[0], total = arr[1];
            res += 1.0 * pass / total;
        }
        return res / classes.length;

    }

    private static int[] c;
    private static int[] a;

    public static List<Integer> countSmallerPro(int[] nums) {
        List<Integer> resultList = new ArrayList<>();
        // 原数组离散化
        discretization(nums);
        // 初始化前缀和数组
        init(nums.length + 5);
        //
        for (int i = nums.length - 1; i >= 0; --i) {
            int id = getId(nums[i]);
            resultList.add(query(id - 1));
            update(id);
        }
        Collections.reverse(resultList);
        return resultList;
    }

    private static void init(int length) {
        c = new int[length];
        Arrays.fill(c, 0);
    }

    private static int lowBit(int x) {
        return x & (-x);
    }

    private static void update(int pos) {
        while (pos < c.length) {
            c[pos] += 1;
            pos += lowBit(pos);
        }
    }

    private static int query(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += c[pos];
            pos -= lowBit(pos);
        }

        return ret;
    }

    /**
     * 离散化
     *
     * @param nums
     */
    private static void discretization(int[] nums) {
        Set<Integer> set = new HashSet<>();
        // 去重
        for (int num : nums) {
            set.add(num);
        }
        int size = set.size();
        a = new int[size];
        int index = 0;

        for (int num : set) {
            a[index++] = num;
        }
        // 排序
        Arrays.sort(a);
    }

    private static int getId(int x) {
        // 二分查找
        return Arrays.binarySearch(a, x) + 1;
    }

    public static int minimumOperations(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                subtract(nums, nums[i], i);
                ans++;
            }
        }
        return ans;
    }

    public static void subtract(int[] nums, int x, int startIndex) {
        int length = nums.length;
        for (int i = startIndex; i < length; i++) {
            nums[i] -= x;
        }
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                if (left == i) {
                    left++;
                    continue;
                }
                if (right == i) {
                    right--;
                    continue;
                }
                int b = nums[left];
                int c = nums[right];
                if (Math.abs(a + b + c - target) < Math.abs(ans - target)) {
                    ans = a + b + c;
                }
                if (a + b + c < target) {
                    left++;
                } else if (a + b + c > target) {
                    right--;
                } else {
                    return ans;
                }
            }
        }
        return ans;
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Set<List<Integer>> set = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (j == i) {
                    continue;
                }
                int b = nums[j];
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    if (left == i || left == j) {
                        left++;
                        continue;
                    }
                    if (right == i || right == j) {
                        right--;
                        continue;
                    }
                    int c = nums[left];
                    int d = nums[right];

                    long temp = (long) (a * 1.0 + b + c + d);
                    if (temp > Integer.MAX_VALUE) {
                        right--;
                    }
                    if (temp == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(a);
                        list.add(b);
                        list.add(c);
                        list.add(d);
                        Collections.sort(list);
                        set.add(list);
                        left++;
                        right--;
                    } else if (temp < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }

    public static int mostFrequentEven(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = -1;
        int num = -1;
        for (int j : nums) {
            if (j % 2 == 1) {
                continue;
            }
            map.merge(j, 1, Integer::sum);
            Integer count = map.get(j);
            if (count > ans) {
                ans = count;
                num = j;
            } else if (count == ans && j < num) {
                num = j;
            }
        }
        return num;
    }

    public static int thirdMax(int[] nums) {
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        int third = Integer.MIN_VALUE;
        int count = 0;
        boolean flag = false;
        for (int num : nums) {
            if (num == Integer.MIN_VALUE && !flag) {
                count++;
                flag = true;
                continue;
            }
            if (num > first) {
                third = second;
                second = first;
                first = num;
                count++;
            } else if (num < first && num > second) {
                third = second;
                second = num;
                count++;
            } else if (num < second && num > third) {
                third = num;
                count++;
            }
        }
        return count <= 2 ? first : third;
    }

    public static long[] findPrefixScore(int[] nums) {
        int max = nums[0];
        long[] convert = new long[nums.length];
        long[] prefix = new long[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            convert[i] = max + nums[i];
            if (i == 0) {
                prefix[i] = convert[i];
            } else {
                prefix[i] = convert[i] + prefix[i - 1];
            }
        }
        return prefix;
    }

    public static int maxDivScore(int[] nums, int[] divisors) {
        int[] score = new int[divisors.length];
        int max = 0;
        int index = -1;
        for (int num : nums) {
            for (int j = 0; j < divisors.length; j++) {
                if (num % divisors[j] == 0) {
                    score[j]++;
                    if (score[j] > max) {
                        max = score[j];
                    }
                }
            }
        }
        for (int j = 0; j < score.length; j++) {
            if (score[j] == max) {
                if (index == -1) {
                    index = j;
                } else if (divisors[j] < divisors[index]) {
                    index = j;
                }
            }
        }
        return divisors[index];
    }
}
